package leetcode.sword;

public class P14_2 {
    public static void main(String[] args) {
//        int sup = 1000000007;
//        long x = 1;
//        for (int i = 0; i < 32; i++) {
//            x = x*2;
//            System.out.print("先不取余数:");
//            System.out.println(x);
////            x = x%sup;
////            System.out.print("取余数:");
////            System.out.println(x);
////            System.out.print("取余后大于sup/3:");
////            System.out.println(x>sup/3);
//
//        }
        System.out.println(cuttingRope(20));
    }

    public static int cuttingRope(int n) {
        //定理： (a*b)%n = ((a%n)*(b%n))%n
        //借助： p14-1的推论，尽可能使长为3的段多
        //java long: MAX_VALUE=9223372036854775807
        //Java int : MAX_VALUE= 2147483647, 而1000000007*3就越界了，所以不够用
        if(n<2){
            return 1;
        }
        if(n==3){
            return 2;
        }
        long result = 1;
        int sup = 1000000007, res = n % 3;
        switch(res){
            case 0: // 3^(n/3)
                for(int i=1;i<=n/3;i++){
                    result = ((result%sup)*3)%sup;
                }
                break;
            case 1: // 3^(n/3-1)*4
                for(int i=1;i<=n/3-1;i++){
                    result = ((result%sup)*3)%sup;
                }
                result = ((result%sup)*4)%sup;
                break;
            case 2:
                for(int i=1;i<=n/3-1;i++){
                    result = ((result%sup)*3)%sup;
                }
                result = ((result%sup)*2)%sup;
                break;
            default:
        }
        return (int)result;
    }
}
